home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group94c.txt / 000009_icon-group-sender _Fri Dec 9 15:27:47 1994.msg < prev    next >
Internet Message Format  |  1995-02-09  |  2KB
  1. Received: by cheltenham.cs.arizona.edu; Fri, 9 Dec 1994 08:46:06 MST
  2. To: icon-group-l@cs.arizona.edu
  3. Date: Fri, 9 Dec 1994 15:27:47 GMT
  4. From: goer@quads.uchicago.edu (Richard L. Goerwitz)
  5. Message-Id: <1994Dec9.152747.7762@midway.uchicago.edu>
  6. Organization: University of Chicago
  7. Sender: icon-group-request@cs.arizona.edu
  8. References: <1994Dec7.221649.10939@cs.sfu.ca>, <JFRIEDL.94Dec9095842@shibuya.nff.ncl.omron.co.jp>
  9. Reply-To: goer@midway.uchicago.edu
  10. Subject: Re: [Q] Algorithm for Regexp Subsumption
  11. Errors-To: icon-group-errors@cs.arizona.edu
  12.  
  13. jfriedl@nff.ncl.omron.co.jp writes:
  14.  
  15. >vorbeck@cs.sfu.ca (Martin Vorbeck) writes:
  16. >|> are there any algorithms out there for checking whether a regular
  17. >|> expression subsumes another one, ie L(E1) is a subset of L(E2)? I have a
  18. >|> "brute-force" solution along these lines:
  19. >|> 
  20. >|> 1. Compute equivalent finite automatas A1 (resp A2) for E1 (resp E2).
  21. >
  22. >Make sure you keep the context of your problem (whetever that might be)
  23. >in mind when doing this.
  24.  
  25. To be sure.  If you create a new DFA, L(E1) or L(E2), then the if you
  26. remove extra states correctly you should end up with the same DFA when
  27. your done if in fact L(E1) is a subset of L(E2).  So in many computa-
  28. tional contexts, the question of whether one is a subset or not is not
  29. important.  Put more succinctly, the regexp a|a* is going to result in
  30. the same DFA as a*, if done "by the book."
  31.  
  32. -- 
  33.  
  34.    -Richard L. Goerwitz              goer@midway.uchicago.edu
  35.     sorry, no witty saying